Fork me on GitHub

ZJOI2017-树状数组

发表于 | | 阅读次数:
字数统计: 1,057

传送门：Zjoi2017-树状数组

吐槽：听说被分到了最简单的题。。。

体节：

我一看，题目中的Find操作像是求后缀异或和，然后打打表发现就是后缀异或和QAQ

那么对于Query(l,r)，Right=XOR（l，r）（l->r的数异或和），Now=XOR（l-1，r-1）。

显然答案是否正确只跟l-1，r的修改次数之和的奇偶性有关，那么我们只需要维护对于每个查询的点对被修改成偶数次的概率就行了。。。

对于Modify（l，r），若（L，R）与（l，r）相交，那么（L，R）这个点对被修改的概率即为$\frac{1}{r-l+1}$。若被覆盖，被修改的概率即为$\frac{2}{r-l+1}$。

那么思路就比较清晰了，以l建外层线段树，以r建内层线段树，矩阵修改（三次），单点查询。因为是线段树上区间操作，而这又是树套树，所以直接下放lazy的复杂度是不对的，我们要用永久化标记，单点查询就是合并一下到根路径上的永久化标记就行了。

但是注意了，还有一个特殊情况没有考虑，就是Query（l，r）时l==1的时候。

此时，Right=XOR（1，r），Now=Find（r）-Find（l-1）=Find（r）-Find（0）=Find（r）=XOR（r，N）

这样的话特判一下，再开个线段树单独维护前缀异或和==后缀异或和的概率就行了

这里介绍一个巧妙的方法（%%%wxh）

Now=XOR（r，N）=XOR（1，N）$\otimes$XOR（1，r-1）

而XOR（1，N）就是总修改次数啊，直接用个cnt就行了

那么特殊情况转换为cnt为奇数时，输出r修改次数为奇数的概率；cnt为偶数时，输出r修改次数为偶数的概率，可以直接用（0，r）这个点对的概率得到

至于修改次数为偶数的概率的合并，无非是$P_{奇} * P_{奇}+P_{偶} * P_{偶}$，然后转换为%998244353意义下就行了

简短的代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
#include<stdio.h>
#include<algorithm>
#include<iostream>
#include<cmath>
#include<cstring>
#define ll long long
#define inf 0x3f3f3f3f
#define P 998244353
#define maxn 200005
using namespace std;
int N,M;
int ls[maxn*400],rs[maxn*400],tot;
int W[maxn*400];//和为奇数的概率
int rt[maxn<<4];
int ksm(int a,int b) {
	int ret=1;
	while(b) {
		if(b&1)ret=1ll*ret*a%P;
		b>>=1,a=1ll*a*a%P;
	}
	return ret;
}
int merge(int a,int b) {
	return (1ll*a*(P+1-b)+1ll*b*(P+1-a))%P;
}
void modify(int &p,int l,int r,int y1,int y2,int D) {
	if(!p)p=++tot;
	if(y1<=l&&y2>=r) {
		W[p]=merge(W[p],D);
		return;
	}
	int mid=l+r>>1;
	if(y1<=mid&&y2>=l)modify(ls[p],l,mid,y1,y2,D);
	if(y2>=mid+1&&y1<=r)modify(rs[p],mid+1,r,y1,y2,D);
}
void Modify(int p,int l,int r,int x1,int x2,int y1,int y2,int D) {
	if(x1<=l&&x2>=r) {
		modify(rt[p],0,N,y1,y2,D);
		return;
	}
	int mid=l+r>>1;
	if(x1<=mid&&x2>=l)Modify(p<<1,l,mid,x1,x2,y1,y2,D);
	if(x2>=mid+1&&x1<=r)Modify(p<<1|1,mid+1,r,x1,x2,y1,y2,D);
}
int query(int p,int l,int r,int y) {
	if(!p)return 0;
	if(l==r)return W[p];
	int mid=l+r>>1;
	int ret=W[p];
	if(y<=mid)ret=merge(ret,query(ls[p],l,mid,y));
	else ret=merge(ret,query(rs[p],mid+1,r,y));
	return ret;
}
int Query(int p,int l,int r,int x,int y) {
	if(l==r)return query(rt[p],0,N,y);
	int mid=l+r>>1;
	int ret=query(rt[p],0,N,y);
	if(x<=mid)ret=merge(ret,Query(p<<1,l,mid,x,y));
	else ret=merge(ret,Query(p<<1|1,mid+1,r,x,y));
	return ret;
}
int main() {
	scanf("%d%d",&N,&M);
	int opt,x,y;
    int cnt=0;
	for(int i=1; i<=M; ++i) {
		scanf("%d%d%d",&opt,&x,&y);
		int inv=ksm(y-x+1,P-2);
		if(opt==1) {
			Modify(1,0,N,x,y,x,y,1ll*2*inv%P);
			Modify(1,0,N,0,x-1,x,y,inv);
			Modify(1,0,N,x,y,y+1,N,inv);
            cnt++;
		}
		if(opt==2) {
            if(x==1&&(cnt&1))printf("%d\n",Query(1,0,N,x-1,y));
			else printf("%d\n",(P+1-Query(1,0,N,x-1,y))%P);
		}
	}
	return 0;
}
0%
``` ```